package jm.algorithm.dp;

/**
 * @Description 0 - 1背包问题
 * @date 2022/5/25 10:14
 */
public class Knapsack {
    public static void main(String[] args) {
        int[] values = {6, 3, 5, 4, 6};
        int[] weights = {2, 2, 6, 5, 4};
        int capacity = 10;
        System.out.println(maxValueExactly(values, weights ,capacity));
    }

    /**
     * dp - 0-1 背包 求最大总价值
     * @param values 价值集合
     * @param weights 重量集合
     * @param capacity 最大容量
     * @return 最高总价值
     */
    static int maxValue(int[] values, int[] weights, int capacity){
        if (values == null || weights == null) return 0;
        if (values.length == 0 || weights.length == 0) return 0;
        if (weights.length != values.length) return 0;
        if (capacity <= 0) return 0;

        int[][] dp = new int[values.length + 1][capacity + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]){ // 无法添加当前物品到背包中
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j],
                            dp[i - 1][j - weights[i -1]] + values[i -1]);
                }
            }
        }
        return dp[values.length][capacity];
    }


    /**
     * dp - 0-1 背包 求最大总价值 - 一维优化
     * @param values 价值集合
     * @param weights 重量集合
     * @param capacity 最大容量
     * @return 最高总价值
     */
    static int maxValue2(int[] values, int[] weights, int capacity){
        if (values == null || weights == null) return 0;
        if (values.length == 0 || weights.length == 0) return 0;
        if (weights.length != values.length) return 0;
        if (capacity <= 0) return 0;

        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = capacity; j >= 1; j--) {
                if (j < weights[i - 1]){ // 无法添加当前物品到背包中
                    dp[j] = dp[j];
                }else {
                    dp[j] = Math.max(dp[j],
                            dp[j - weights[i -1]] + values[i -1]);
                }
            }
        }
        return dp[capacity];
    }


    /**
     * dp - 0-1 背包 求最大总价值 - 结构优化
     * @param values 价值集合
     * @param weights 重量集合
     * @param capacity 最大容量
     * @return 最高总价值
     */
    static int maxValue3(int[] values, int[] weights, int capacity){
        if (values == null || weights == null) return 0;
        if (values.length == 0 || weights.length == 0) return 0;
        if (weights.length != values.length) return 0;
        if (capacity <= 0) return 0;

        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = capacity; j >= weights[i - 1]; j--) {
                    dp[j] = Math.max(dp[j],
                            dp[j - weights[i -1]] + values[i -1]);
            }
        }
        return dp[capacity];
    }


    /**
     * dp - 0-1 背包 恰好装满 求最大总价值
     * @param values 价值集合
     * @param weights 重量集合
     * @param capacity 最大容量
     * @return 最高总价值
     */
    static int maxValueExactly(int[] values, int[] weights, int capacity){
        if (values == null || weights == null) return 0;
        if (values.length == 0 || weights.length == 0) return 0;
        if (weights.length != values.length) return 0;
        if (capacity <= 0) return 0;

        int[] dp = new int[capacity + 1];

        // 初始值全为最小值
        for (int j = 1; j <= capacity; j++) {
            dp[j] = Integer.MIN_VALUE;
        }
        
        for (int i = 1; i <= values.length; i++) {
            for (int j = capacity; j >= weights[i - 1]; j--) {
                dp[j] = Math.max(dp[j],
                        dp[j - weights[i -1]] + values[i -1]);
            }
        }
        return dp[capacity] < 0 ? -1 : dp[capacity];
    }
}
